﻿// Ideal Path UVA - 1599.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>


/*
* https://vjudge.net/problem/UVA-1599
新迷失之地游乐园（New Lostland amusement park）的新迷宫景点已经开放。迷宫由 n 个房间组成
由 m 个通道连接而成。每条通道都被染成不同的颜色。
. 迷宫的游客
他们的目标是到达位于 n 号房间的迷宫出口。
的迷宫出口。
迷宫主人计划明天举行一次比赛。几名选手将被投放到
1 号房间。他们将在跑向 n 号房间时写下通道的颜色。
颜色。颜色顺序最短的选手就是比赛的获胜者。如果
如果有几位选手的颜色序列长度相同，则路径最理想的选手获胜。如果
如果颜色序列在最短路径中是词典最小的，那么这条路径就是理想路径。
安德鲁正在为比赛做准备。他乘坐直升机游览了新迷失之地的上空，并制作了一张
迷宫的照片。你的任务是帮助他找到从 1 号房间到
你的任务是帮助他找到从 1 号房间到 n 号房间的理想路径，使他赢得比赛。
注：一个序列 (a1, a2, ... , ak) 在词法上比一个序列 (b1, b2, ... , bk) 小，如果有
存在 i，使得 ai < bi
且所有 j < i 时 aj = bj。
输入
输入文件包含多个测试用例，每个测试用例如下所述。
输入文件的第一行包含整数 n 和 m - 房间数和通道数、
分别为房间数和通道数（2 ≤ n ≤ 100000，1 ≤ m ≤ 200000）。下面的 m 行描述的是段落，每个段落
用三个整数描述：ai
, bi
和 ci - 它连接的房间数和它的
颜色（1 ≤ ai
，bi ≤ n，1 ≤ ci ≤ 109
). 每个通道可以从任一方向通过。两个房间可以
两个房间之间可以有多条通道相连，也可以有一条通道从一个房间通向另一个房间。保证
可以从 1 号房间到达 n 号房间。
输出
每个测试用例的输出必须符合以下说明。
输出文件的第一行必须包含 k - 从房间号 1 到房间号 n 的最短路径长度。
第二行必须包含 k 个数字--通道的颜色，其顺序为
在理想路径中必须依次通过的通道的颜色。
输入示例
4 6
1 2 1
1 3 2
3 4 3
2 3 1
2 4 4
3 1 1
样本输出
2
1 3
*/
int main()
{
    std::cout << "Hello World!\n";
}

 